package com.zjl.redis.第14章_大数据统计;



/**
 * 为了解决布隆过滤器不能删除元素的问题，布谷鸟过滤器横空出世。
 *
 * ●删除不完美，存在误删的概率。删除的时候只是删除了一份指纹副本， 并不能确定此指纹副本是要删除的key的指纹。
 * 同时这个问题也导致了假阳性的情况。
 *
 * ●插入复杂度比较高。随着插入元素的增多,复杂度会越来越高，
 * 因为存在桶满，踢出的操作,所以需要重新计算，但综合来讲复杂度还是常数级别。
 *
 * ●存储空间的大小必须为2的指数的限制让空间效率打了折扣。
 * 同一个元素最多插入kb次，(k指哈希函数的个数, b指的是坐标下能装指纹的个数也可以说是坐标下桶的尺寸大小)
 * 如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。
 * 插入同一项kb+ 1次将导致插入失败。这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。
 *
 * fp = fingerprint(x)
 * h1 = hash(x)
 * h2 = h1 ^ hash(fp)  // 异或
 *
 * h1 是第一个槽位
 * h2 是备用的槽位
 *
 */
public class C5_布谷鸟过滤器 {
    public static void main(String[] args) {
        String xxx = "485x468548564wdefw85qe4tgf68e7r4hy68rte";
        //我也可以
        int a = xxx.toCharArray().hashCode();//哈希1
        int b = xxx.hashCode();//哈希2
        int c = a^b;//哈希3
        System.out.println("a = " + (c^b));
        System.out.println("b = " + (c^a));
        System.out.println("c = " + c);

    }

    //指纹信息  此算法不对，需要另请其他算法
    private static int fingerprint(String key) {
        return key.toCharArray().hashCode();
    }
}
